package com.example.leetcode.solution;

import com.example.leetcode.ListNode;

class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length < 2) {
            return lists[0];
        }
        ListNode result = lists[0];

        for (int i = 1; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }

    public ListNode getTail(ListNode l) {
        while (l.next != null) {
            l = l.next;
        }
        return l;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val > l2.val) {
            ListNode l3 = l2;
            l2 = l1;
            l1 = l3;
        }

        ListNode node1 = l1;
        ListNode node2 = l2;
        ListNode pre = node1;
        while (node1 != null && node2 != null) {
            ListNode next1 = node1.next;
            while (node1.val < node2.val && next1 != null && next1.val < node2.val) {
                pre = node1;
                node1 = node1.next;
                next1 = node1.next;
            }
            if (node1.val <= node2.val) {
                ListNode next2 = node2.next;
                node1.next = node2;
                node2.next = next1;
                node2 = next2;
                pre = node1.next;
                node1 = next1;
            } else {
                next1 = node1;
                node1 = pre;
                ListNode next2 = node2.next;
                node2.next = next1;
                node1.next = node2;
                pre = node2;
                node2 = next2;
                node1 = next1;
            }
        }
        if (node1 == null && node2 != null) {
            pre.next = node2;
        }
        return l1;
    }
}
